class Solution {
    double ret, sum, target;
    void dfs(vector<int> &nums)
    {
        if(sum >= target)
        {
            if(sum == target)
                ret++;
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            dfs(nums);
            sum -= nums[i];
        }
    }
public:
    int combinationSum4(vector<int>& nums, int _target) {
        // 这种是回溯的做法，时间复杂度过高
        // target = _target;
        // dfs(nums);
        // return ret;

        // 下面是动态规划的做法
        int n = nums.size();
        // dp[i]表示凑成i，一共有多少排列数
        vector<double> dp(_target + 1);

        // 初始化dp[0]，dp[0]表示凑成0一个有多少排列数，只有啥都不选这种做法，那就是1
        // 也可以理解为保证后续填表的正确性
        dp[0] = 1;
        
        for(int i = 1; i <= _target; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(nums[j] <= i)
                    dp[i] += dp[i - nums[j]];
            }
        }

        return dp[_target];
    }
};